package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/16 12:10
 * @description：https://leetcode-cn.com/problems/maximum-number-of-visible-points/
 */
public class 可见点的最大数目 {
    @Test
    public void test() {
        Solution solution = new Solution();
        List<List<Integer>> points = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        list.add(2);
        list.add(1);
        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(2);
        list2.add(2);
        ArrayList<Integer> list3 = new ArrayList<>();
        list3.add(3);
        list3.add(3);
        points.add(list);
        points.add(list2);
        points.add(list3);
        List<Integer> location = new ArrayList<>();
        location.add(1);
        location.add(1);
        System.out.println(solution.visiblePoints(points, 90, location));
    }

    class Solution {
        public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
            int x = location.get(0), y = location.get(1);
            double pi = Math.PI, t = angle * pi / 180;
            int count = 0;
            ArrayList<Double> list = new ArrayList<>();
            for (List<Integer> point : points) {
                Integer x1 = point.get(0);
                Integer y1 = point.get(1);
                if (x == x1 && y == y1) {
                    count++;
                    continue;
                }
                list.add(Math.atan2(x1 - x, y1 - y) + pi);
            }
            Collections.sort(list);
            int n = list.size();
            int max = 0;
            for (int i = 0; i < n; i++) {
                list.add(list.get(i) + 2 * pi);
            }
            for (int i = 0, j = 0; j < n * 2; j++) {
                while (i < j && list.get(j) - list.get(i) > t) i++;
                max = Math.max(max, j - i + 1);
            }
            return max + count;
        }
    }
}
